#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& nums, int target){
    int l = 0, r = nums.size() - 1, mid;
    while(l <= r){
        mid = l + (r-l)/2;
        if(nums[mid] < target) l = mid + 1;
        else if(nums[mid] > target) r = mid -1;
        else return mid;
    }
    return -1;
}

int leftBound(const vector<int>& nums, int target){
    int l = 0, r = nums.size()-1, mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(nums[mid] >= target) r = mid - 1;
        else l = mid + 1;
    }
    if(l == nums.size() || nums[l] != target) return -1;
    return l;
}

int rightBound(const vector<int>& nums, int target){
    int l = 0, r = nums.size()-1, mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(nums[mid] <= target) l = mid + 1;
        else r = mid - 1;
    }
    if(r == -1 || nums[r] != target) return -1;
    return r;
}